#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int wss = words.size(), ws = words[0].size(), n = target.size(), mod = 1e9 + 7;
        vector<vector<int>> count(ws + 1, vector<int>(26));
        for (int j = 1; j <= ws; j++)
            for (int i = 0; i < wss; i++) count[j][words[i][j - 1] - 'a']++;
        vector<vector<int>> dp(ws + 1, vector<int>(n + 1));
        for (int j = 0; j <= ws; j++)
            dp[j][0] = 1;

        for (int j = 1; j <= ws; j++) {
            for (int k = 1; k <= n; k++) {
                dp[j][k] = (dp[j][k] + dp[j - 1][k]) % mod;
                if (count[j][target[k - 1] - 'a'])
                    dp[j][k] = (dp[j][k] + (long long)count[j][target[k - 1] - 'a'] * dp[j - 1][k - 1]) % mod;
            }

        }
        // for (int x = 0; x <= ws; x++) {
        //         for (int y = 0; y <= n; y++)
        //             cout << dp[x][y] << ' ';
        //         cout << endl;
        //     }
        //     cout << endl;
        return dp[ws][n];
    }
};